#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""

"""
FARMER = 0
WOLF = 1
LAMB = 2
VEGE = 3


class FarmerRiver:
    def __init__(self):
        self.left = [1, 1, 1, 1]        # farmer, wolf, lamb, vege
        self.right = [0, 0, 0, 0]     # right可以根据left计算

        self.true_path = []                 # 记录正确路线
        self.all_solution = []              # 所有方案

        self.true_path.append( tuple(self.left) )
        self.fail_left_state = set()                 # 记录不可能成功的中间状态.
        self.left_history = set()          # right可以根据left计算出
        self.left_history.add( tuple(self.left) )
        # self.left_history = []

        ret = self.goto_right()
        print("ret ", ret)

    def get_valid_goto_right_states(self):
        self.go_farmer()        # 农民必须移动

        if self.valid_state(self.left) and self.valid_state(self.right):
            # 只移动农夫
            print("succ goto right", self.left, self.right)
            yield self.left, self.right

        for idx in range(1, 4):
            if self.left[idx] == 1:

                # 这里修改left和right应该没事, 调用方和这里都会恢复.
                assert self.right[idx] + self.left[idx] == 1
                self.left[idx] = 0
                self.right[idx] = 1

                # right肯定安全, 应为农夫为1
                if self.valid_state(self.left) and self.valid_state(self.right):
                    print("succ goto right", self.left, self.right)
                    yield self.left, self.right

                # 恢复
                self.left[idx] = 1
                self.right[idx] = 0


    def get_valid_goto_left_states(self):
        self.go_farmer()        # 农民必须移动

        # 做法和 get_valid_goto_right_states 相反(left, right交换即可)
        # copy_left =
        if self.valid_state(self.left) and self.valid_state(self.right):
            # 只移动农夫
            print("succ goto left", self.left, self.right)
            yield self.left, self.right

        for idx in range(1, 4):
            if self.right[idx] == 1:

                assert self.right[idx] + self.left[idx] == 1
                self.right[idx] = 0
                self.left[idx] = 1

                # left肯定安全, 应为农夫为1: 可以省略self.valid_state(self.left)
                if self.valid_state(self.left) and self.valid_state(self.right):
                    # print("succ ", self.left, self.right)
                    print("succ goto left", self.left, self.right)
                    yield self.left, self.right
                # else:
                    # print("failed ", self.left, self.right)

                # 恢复
                self.right[idx] = 1
                self.left[idx] = 0

    def valid_state(self, state):
        # 农夫在, 都安全
        if state[FARMER] == 1:
            return True

        # 以下为农夫不在的情况
        if state[WOLF] == 1 and state[LAMB] == 1:
            return False

        if state[LAMB] == 1 and state[VEGE] == 1:
            return False

        return True

    def goto_left(self):
        # self.go_farmer()

        origin_left = list(self.left)
        origin_right = list(self.right)
        origin_path = list(self.true_path)

        for (left_state, right_state) in self.get_valid_goto_left_states():
            assert self.left[0] == 1

            if tuple(left_state) in self.fail_left_state:
                continue

            # 不要来回走相同路径
            if tuple(left_state) in self.true_path:
                continue

            # 去左岸, 左岸必然还有东西存在(不然在goto_right那里判断时就结束了)
            # if self.left == [0, 0, 0, 0]:
            #     self.true_path.append( tuple(self.left) )
            #     return True

            assert self.left[0] == 1 and self.right[0] == 0


            self.left = left_state
            self.right = right_state
            self.true_path.append(tuple(self.left))

            print('try left : ', left_state)
            print('try right: ', right_state)
            print('true path: ', self.true_path)


            # if self.goto_right():
            #     return True
            self.goto_right()

            self.true_path = list(origin_path)


        self.left = list(origin_left)
        self.right = list(origin_right)
        # self.fail_left_state.add(tuple(origin_left))
        # return False
        # 如果没有成功, 恢复left, right

    def goto_right(self):
        # NOTE: 整个算法的入口

        origin_left = list(self.left)
        origin_right = list(self.right)
        origin_path = list(self.true_path)

        for (left_state, right_state) in self.get_valid_goto_right_states():
            assert self.right[0] == 1

            if tuple(left_state) in self.fail_left_state:
                continue

            if tuple(left_state) in self.true_path:
                continue

            assert self.right[0] == 1
            if self.left == [0, 0, 0, 0]:
                self.true_path.append( tuple(self.left) )
                self.all_solution.append( list(self.true_path) )
                self.true_path.pop()
                continue

            self.left = left_state
            self.right = right_state

            self.true_path.append(tuple(left_state))

            print('try left : ', self.left)
            print('try right: ', self.right)
            print('true path: ', self.true_path)

            # if self.goto_left():
            #     return True
            self.goto_left()

            self.true_path = list(origin_path)        # 在goto_left处理即可

        self.left = list(origin_left)
        self.right = list(origin_right)
        # print('return false', self.right)

        # return False

    def go_farmer(self):
        # farmer河岸两侧左右移动
        self.left[0] = 1 - self.left[0]
        self.right[0] = 1 - self.right[0]


def main():
    print("start main")
    f = FarmerRiver()
    print(f.all_solution)
    print(f.true_path)
    print(f.fail_left_state)

if __name__ == "__main__":
    main()
